The present invention is directed to communications networking. It is directed particularly to providing routing for private wide-area networks.
1. Private Wide-Area Networks
An enterprise that has many sites can build a private wide-area network by placing routers at each site and using leased lines to interconnect them. A router that has a wide-area connection to another router may be called a xe2x80x9cbackbone router.xe2x80x9d The xe2x80x9cbackbone networkxe2x80x9d is the set of backbone routers and their interconnections.
If every backbone router is connected to every other backbone router, the back-bone network is said to be xe2x80x9cfully meshed.xe2x80x9d In a fully meshed backbone network, data that travel from one site to another go through the backbone router at an origin site (xe2x80x9cingress routerxe2x80x9d), travel over the leased line to the backbone router at the target site (xe2x80x9cegress routerxe2x80x9d), and then enter the target site. More commonly, though, the backbone network is not fully meshed; a router is connected to only a small number of others (three or four). In such a sparse topology, the ingress and egress routers may not be directly connected. In this case, data may have to pass through several additional, xe2x80x9ctransitxe2x80x9d routers on the way from ingress to egress.
In a private network like this, the design and operation of the backbone network is the responsibility of the enterprise. A routing algorithm must run in the backbone routers, enabling them to tell each other the addresses of the destinations to which they can respectively afford access.
It is worth noting that a leased line is not actually a piece of wire going from one site to another. It is really a circuit through some circuit-switching network. But this is of no import to the enterprise network manager, to whom those circuits can be considered simple unstructured pipes. Conversely, although the telephone network itself requires considerable management, the telephone-network managers do not need to know anything about the enterprise backbone network; to them, the telephone network just provides point-to-point connections. They do not need to know what role these connections might be playing in an enterprise data network.
We may say that the enterprise network is xe2x80x9coverlaidxe2x80x9d on top of the telephone network. The enterprise network can be called the xe2x80x9chigher layerxe2x80x9d network, the telephone network the xe2x80x9clower layerxe2x80x9d network. Both networks exist, but each is transparent to the other. The enterprise""s backbone routers exchange routing information with each other, but the telephone switches do not store or process that routing information. That is, backbone routers are xe2x80x9crouting peersxe2x80x9d of each other, but they are not routing peers of the telephone switches. This way of building a higher-layer network on top of a lower-layer network is called the xe2x80x9coverlay model.xe2x80x9d
2. Virtual Private Networks
Wide-area enterprise networks are now more likely to be built on top of frame-relay and ATM networks than on top of circuit-switched (telephone) networks. Whereas a telephone network really provides circuits between backbone routers, a frame-relay or ATM network provides xe2x80x9cvirtual circuitsxe2x80x9d between backbone routers. But this changes nothing as far as the enterprise""s routing task is concerned; the overlay model still applies even though the lower-layer network is now a frame-relay or ATM network rather than a circuit-switched one, i.e., even though virtual rather than fixed circuits make the point-to-point connections between backbone routers. The two networks are still transparent to each other. The enterprise network manager still has a wide-area backbone to design and operate. However, because the circuits are xe2x80x9cvirtual,xe2x80x9d this is usually called a xe2x80x9cvirtual private networkxe2x80x9d (VPN) instead of a xe2x80x9cprivate network.xe2x80x9d
Since the two networks are transparent to each other in the overlay model, that model is distinguished by the fact that the enterprise""s backbone routers do not share with the (service provider""s ) frame-relay or ATM switches the routing information that they must share with each other. This causes inefficiency when the enterprise""s backbone routers are not fully meshed. In such networks, some packets go from the ingress router through one or more transit routers before they reach the egress router. At each one of these xe2x80x9chops,xe2x80x9d the packet leaves the frame-relay or ATM network and then enters it again. This is sub-optimalxe2x80x94there is little value in having a packet go in and out of the frame-relay or ATM network multiple times.
This problem can be avoided by making the enterprise backbone fully meshed, but that causes problems of its own. The number of virtual circuits the enterprise has to pay the service provider for to make the network fully meshed grows as the square of the number of backbone routers. Apart from the cost, routing algorithms tend to scale poorly as the number of direct connections between routers grows. This causes additional problems.
The overlay model also tends to result in extra traffic when multicast is in use. It is usually impractical or undesirable for the xe2x80x9clower layerxe2x80x9d network to do the necessary packet replication, so all packet replication must be done in the xe2x80x9chigher layerxe2x80x9d network, even if a number of replicated packets must then follow the same xe2x80x9clower layerxe2x80x9d path up to a point.
3. The Peer Model
Since these considerations all impose upon the resources of an enterprise for which communications is not necessarily a core competence, a service provider (xe2x80x9cSPxe2x80x9d) can afford its customers greater value if it absorbs the task of designing and operating the backbone. More specifically, the SP should so organize and operate the backbone that, from the point of view of a particular site administrator, every enterprise network address not located at a (given site is reachable through the SP""s backbone network. How the SP""s backbone decides to route the traffic is the SP""s concern, not that of the customer enterprise. So the customer enterprise does not really need to maintain a backbone router at each site; it just needs a router that attaches to one of the SP""s backbone routers. As will become apparent, providing such an organization involves abandoning the overlay model for a different model. For reasons that will be set forth below, we call the new model the xe2x80x9cpeer model.xe2x80x9d
Terminology:
C-network: the enterprise network, consisting of C-routers, which are maintained and operated by the enterprise.
P-network: the SP network, consisting of P-routers, which the SP maintains and operates.
CE-router: an xe2x80x9cedge routerxe2x80x9d in the C-network, i.e., a C-router that attaches directly to a P-router and is a routing peer of the P-router.
PE-router: an xe2x80x9cedge routerxe2x80x9d in the P-network, i.e., a P-router that attaches directly to a C-router and is a routing peer of the C-router.
If a P-router is not a PE-router, i.e., not an edge router, it is a transit router. The concept of edge and transit routers is relative to specific VPNs. If a given one of the SP""s routers receives a given VPN""s traffic from and forwards it to only others of the SP""s routers, the given router is a transit router vis-à-vis the given VPN. Yet that same router may receive another VPN""s traffic from and/or forward it to one of that other VPN""s edge routers, in which case the given SP router is an edge router from the other VPN""s point of view.
In the conventional peer model, where xe2x80x9cvirtual routersxe2x80x9d (i.e., one instance of the routing algorithm per VPN) are used, all C-routers within the same VPN are routing peers of each other. But two C-routers will be routing adjacencies of each other only if they are at the same site. Each site has at least one CE router, each of which is directly attached to at least one PE router, which is its routing peer. Since CE routers do not exchange routing information with each other, there is no virtual backbone for the enterprise to manage, and there is never any need for data to travel through transit CE routers. Data go from the ingress CE router through a sequence of P-routers to the egress CE router. So the resultant routing is optimal. These clear customer benefits have led certain SPs to adopt the peer model.
The conventional peer-model approach also enables the SP to solve certain problems that arise from using a common backbone network for more than one client. One of these is address duplication. Although there is an international assigned-number authority from which unique addresses can be obtained, many enterprise networks simply assign their private-network addresses themselves. So their addresses are unique only within the particular enterprise: they may duplicate addresses that another customer enterprise uses. An SP trying to use, say, an Internet-Protocol (xe2x80x9cIPxe2x80x9d) backbone as the backbone for different enterprise networks having overlapping address spaces needs to provide its P-routers with a way of identifying and selecting a route to the one of potentially many same-address destinations to which it should forward a packet.
So the SP makes use of a xe2x80x9cvirtual router.xe2x80x9d When a PE router receives a packet received from a CE router, the PE router xe2x80x9ctagsxe2x80x9d the packet with an indication of the C-network where it originated. It then bases its determination of what router to forward the packet to not only on the packet""s destination address but also on the identity of the originating C-network. At each subsequent hop, the router looks up the packet""s destination address in the forwarding table specific to the C-network that the tag designates.
This also solves another multiple-customer problem, that of the access control. If an enterprise buys network-backbone service from an Internet SP, it wants some assurance that its network receives only packets that originated in its own network. It also wants to be sure that packets originating in its network do not leave the enterprise network by accident. Of course, two enterprises might want to be able to communicate directly, or to communicate over the Internet. But they want such communication to occur only through xe2x80x9cfirewalls.xe2x80x9d By using the virtual router, the SP solves this problem, too.
We have devised a way for an SP to provide its customers the peer model""s advantages at costs considerably lower than those that the conventional virtual-router approach exacts. The way in which we do this enables transit P-routers to base their routing decisions for VPN-destined packets on packet fields that the transit routers interpret without reliance on VPN-specific routing information.
To appreciate the resultant improvement, one must recognize that one of the main problems in large IP backbones is the quantity of resources (memory, processing, band-width) needed to maintain the routing information. If an SP now adds parallel routing information for, say, a hundred C-networks, the virtual-router approach requires that each physical P-router act as a hundred xe2x80x9cvirtualxe2x80x9d C-routers. That is, each P-router runs one-hundred routing algorithms (one for each C-network), maintains one-hundred forwarding tables, etc. Clearly, this greatly exacerbates the existing information-maintenance problem.
Indeed, because of poor topological matching, the problem is even worse than it appears at first glance. SPs generally try to assign addresses in a topologically meaningful way. That is, the address a system has should be related to where it attaches to the SP""s network. This sort of addressing scheme allows routing information to be aggregated; if addresses of links that are topologically close tend to have the same high-order bits, for instance, a single routing-table entry can be used for a large number of relatively close destinations. Such aggregation reduces the routing load on the P-routers.
But many customer enterprises"" networks have addressing schemes that do not map well to the SP""s backbone topology. So passing enterprise routing information into the P-network, as a peer-model organization does by definition, exacerbates routing-information overload.
And the virtual-router approach introduces a problem of its own. The C-network""s interior-routing algorithm is now running both in C-routers and in P-routers. This blurs the administrative boundaries. If the routing algorithm fails, two different administrations must work together to troubleshoot it. This is in direct contradiction to a lesson of nearly all networking experience: interior-routing algorithms must be confined to a single administrative domain.
We greatly reduce these problems by a judicious use of packet tagging. PE routers in systems that implement the present invention""s teachings still use VPN-specific routing information in making their routing decisions, so they still must maintain tables of such VPN-specific information. But they relieve transit routers of the need to do so. When a PE router receives a packet from a customer enterprise, it provides the packet with an internal-routing field, which a transit router can interpret as specifying the egress PE router that will forward the packet into the remotely located part of the customer-enterprise network. For example, the internal-routing field may include a tag that the transit router can interpret as specifying the next router on the way to that egress PE router. Consequently, transit routers need not concern themselves with routes to locations in the customer enterprises"" networks. Yet the egress PE router can still determine the particular VPN into which it is to forward the packet, because the first PE router. which can identify the VPN by the CE router from which it received the packet, so forms the internal-routing field""s contents that it additionally specifies the target VPN. For example, the internal-routing field can include a second tag, one that the egress router can interpret as identifying the CE router that affords access to the addressed host in the proper VPN.